import collections
from typing import List


class Solution:
    def maxWeight(self, edges: List[List[int]], value: List[int]) -> int:
        # 生成无向图的邻接列表结构（每个点只记录比它下标大的邻边）
        graph = collections.defaultdict(set)
        for n1, n2 in edges:
            if n1 > n2:
                n1, n2 = n2, n1
            graph[n1].add(n2)

        # ---------- 寻找无向图中的三角形 ----------
        triangle_by_point_max = collections.defaultdict(list)  # 当前点构成的最大三角形（用于两个三角形完全重合的情况）
        triangle_by_point = collections.defaultdict(list)  # 当前点能构成的所有三角形
        triangle_by_edge = collections.defaultdict(list)  # 当前边能构成的前三大的三角形

        for i in range(len(value)):  # 遍历所有顶点
            for j in graph[i]:  # 遍历顶点的邻边的顶点（根据无向图的性质，有:i<j)
                for k in list(graph[i] & graph[j]):  # 遍历所有与i和j能构成三角形的点（根据无向图的性质，有:i<j<k)
                    # 计算并缓存三角形的喜爱度得分
                    triangle_mark = value[i] + value[j] + value[k]

                    triangle_info = [i, j, k, triangle_mark]

                    for n in [i, j, k]:  # 遍历三角形的3个顶点
                        # 更新三个三角形顶点构成的最大三角形
                        if not triangle_by_point_max[n] or triangle_by_point_max[n][-1] < triangle_mark:
                            triangle_by_point_max[n] = triangle_info

                        # 更新三个三角形顶点构成的所有三角形
                        triangle_by_point[n].append([i, j, k])

                    for edge in [(i, j), (i, k), (j, k)]:  # 遍历三角形的3条边
                        # 更新三角形三条边构成的前三大的三角形
                        triangle_by_edge[edge].append(triangle_info)
                        triangle_by_edge[edge].sort(key=lambda x: x[-1], reverse=True)
                        if len(triangle_by_edge[edge]) > 3:
                            triangle_by_edge[edge].pop()

        #  ---------- 拼接无向图中的三角形 ----------
        ans = 0

        for i in range(0, len(value)):  # 遍历所有顶点
            # 当前点没有三角形的情况
            if not triangle_by_point_max[i]:
                continue

            max_triangle = triangle_by_point_max[i]  # 当前顶点的最大三角形

            # 【三角形拼接的情况】
            # 已知△xab是包含x的最大三角形，不妨设以x为中心的最优解的两个三角形为△xpq和△xrt
            # 1. 如果a和b都不在pqrt中，那么直接将其中一个三角形换成△xab可获得更优解
            # 2. 如果a和b有一个在pqrt中，那么将对应的那个三角形换成△xab可获得更优解
            # 所以a和b一定同时在pqrt中，可能在一个三角形中，也可以不在也可以三角形中，于是得出以下3种情形：

            # [情形1]最大三角形△xab的两个顶点a和b在同一个三角形中，且当前点只有这一个三角形：两个三角形完全重合的情况
            ans = max(ans, max_triangle[-1])

            # [情形2]最大三角形△xab的两个顶点a和b在同一个三角形中，且当前点还有其他三角形：两个三角形共用一个顶点、一个邻边或重合
            for info in triangle_by_point[i]:
                ans = max(ans, sum(value[x] for x in set(max_triangle[:3]) | set(info[:3])))
                # ans = max(ans, self.count_val(max_triangle, info))

            # [情形3]最大三角形△xab的两个顶点a和b在不同三角形中（分别以a和b寻找三角形）：两个三角形共用一个顶点
            max_points = max_triangle[:3]
            max_points.remove(i)
            edge1, edge2 = [(i, x) if i < x else (x, i) for x in max_points]

            for info1 in triangle_by_edge[edge1]:
                for info2 in triangle_by_edge[edge2]:
                    ans = max(ans, sum(value[x] for x in set(info1[:3]) | set(info2[:3])))

        return ans


if __name__ == "__main__":
    # 6
    print(Solution().maxWeight(edges=[[0, 1], [1, 2], [0, 2]], value=[1, 2, 3]))

    # 0
    print(Solution().maxWeight(edges=[[0, 2], [2, 1]], value=[1, 2, 5]))

    # 39
    print(Solution().maxWeight(
        edges=[[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [1, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]],
        value=[7, 8, 6, 8, 9, 7]))

    # 31903
    print(Solution().maxWeight(
        edges=[[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [0, 8], [0, 9], [1, 2], [2, 3], [3, 4], [4, 5],
               [5, 6], [6, 7], [7, 8], [8, 9], [1, 9]],
        value=[4304, 3170, 7710, 7158, 9561, 934, 3100, 279, 1817, 5336]
    ))
